This invention relates to synchronizing the clocks of devices, such as independent continuous bit stream oriented (CBO) data terminals, in a communications network in which packets of data are sent over the network.
Typically, such a communications network includes a number of nodes interconnected by links, each node serving one or more data terminals. The nodes each function as a so-called "concentrator" to arrange data to be transmitted from one of its terminals to a terminal served by another node into discrete packets for transmission over the one or more links between the nodes. The node inserts a "header" in each packet (that may identify the originating terminal and the destination terminal) along with a predetermined number of bits of data, and a "trailer" to indicate the end of the packet. To prevent and/or deal with collisions between packets on the network, the nodes transmit their packets in an asynchronous manner, for example, according to a predetermined transmission protocol (e g., X.25, etc.). The nodes generally transmit the packets at a rate (such as 64,000 bits/second) that is higher than that used by the terminals (e.g., 9,600 bits/second). The receiving node stores incoming packets in a buffer until they are retrieved by the destination terminal.
Some types of data terminals used in such a communication network transmit data noncontinuously in bursts The clocks in these types of terminals are synchronized during the relatively frequent idle intervals between transmissions.
Other kinds of data terminals transmit data and expect to receive data continuously. These terminals, known as continuous bit stream oriented (CBO) terminals, do not provide a regularly occurring, idle interval during which their clocks can be synchronized. When the clocks of transmitting and receiving CBO terminals are not synchronized, the receiving CBO terminal will retrieve data from the buffer of its node either more slowly or more rapidly than data from the transmitting terminal is placed into the buffer. If this persists, the buffer will eventually overflow or be emptied, leading to loss of transmitted data in the former case or, in the case of the latter, display of incorrect data by the receiving terminal (which continues to "retrieve" data from the empty buffer).
Synchronization of the clocks of the CBO terminals is complicated by the fact that the received bit stream does not directly indicate the timing of the transmitting CBO terminal. Also, the intervals between the arrivals of successive packets vary because the network may itself introduce random (i.e., stochastic) delays during the transmission of different packets. Further, the nodes may add to the variability of packet arrival times by multiplexing transmission of data packets from CBO terminals with data packets from other types of data terminals in the network.
One synchronization scheme, described in "Terminal Synchronization in Asynchronous Networks," by DePrycker et al, IEEE International Conference on Communications, June, 1987, pages 800-807, monitors the level of (i.e., the number of packets in) the data buffer of the receiving node to determine the time taken for the buffer level to change by one packet. To avoid errors caused by stochastic network delays in which fluctuations in the filling level of the buffer also vary due to the stochastic interarrival times between packets, the buffer level is measured each time that a packet is removed and that level is averaged over a predetermined interval. When the expected buffer level shows a change of one half of a packet (determined from the average buffer level in a statistical sense to any desired level of confidence) the buffer size is deemed to have grown by one packet. The time taken for this to happen indicates the frequency offset between the transmitting and receiving terminals. The clock of the receiving terminal is then adjusted by twice this amount in the proper direction to restore the buffer level. Then, the clock is readjusted to the frequency which would remove the calculated offset and the measurement and adjustment procedure begins again.